package com.wyp168.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @ClassName MaxChunksToSortedSolution
 * @Title TODO
 * @Description TODO
 * @Author wyp168
 * @Date 2022/10/13 09:07
 */
public class MaxChunksToSortedSolution {
    public static void main(String[] args) {
        MaxChunksToSortedSolution solution = new MaxChunksToSortedSolution();
        int[] arr = {1,0,2,3,4};

        System.out.println(solution.maxChunksToSorted(arr));
    }

    public int maxChunksToSorted(int[] arr) {
        Deque<Integer> queue = new ArrayDeque<>();

        for (int i = 0; i < arr.length; i++) {
            if (queue.isEmpty() || queue.peek() < arr[i]) {
                queue.push(arr[i]);
                continue;
            }
            int currMaxBlock = queue.pop();

            while (!queue.isEmpty() && queue.peek() > arr[i]) {
                queue.pop();
            }
            queue.push(currMaxBlock);
        }
        return queue.size();
    }
}
